1. Field of the Invention
The present invention relates in general to an apparatus and method for DBWRR (Delay Bound Weighted Round Robin) cell scheduling in an ATM (Asynchronous Transfer Mode) switch, and more particularly to an apparatus and method for DBWRR cell scheduling in a high-speed ATM switch which can meet requirements for a cell transfer delay of real-time traffic in the ATM switch and minimize a processing overhead of the switch.
2. Description of the Related Art
Up until recently, because of economical and technical problems, little interest has been aroused in studies of provision of existing telephone-class voice and facsimile services, such as a POTS (Plain Old Telephone Service), over an ATM network.
Recently, however, with the development of an IMT-2000 system employing an ATM technique as its main technique, users, mostly business subscribers, have increasingly demanded an integrated solution capable of providing voice services integrated on an ATM WAN (Wide Area Network)/LAN (Local Area Network), resulting in studies being actively conducted of cell transfer over the ATM network.
For real-time services, such as a VTOA (Voice and Telephony over ATM) used in the IMT-2000 system, a cell is discarded just when a transfer delay thereof exceeds a predetermined maximum bound. In this regard, the cell transfer delay has a great effect on the quality of service.
For reference, in ITU-T (International Telecommunication Union-Telecommunication Sector) recommendation G.114, it is recommended that the maximum allowable delay time be about 150 ms with respect to connections under echo control and about 25 ms with respect to connections under no echo control.
Delay-sensitive traffic, more particularly voice traffic must satisfy the quality of service associated with the cell transfer delay ahead of other service qualities. This requirement must in turn be reflected on cell scheduling. Note that a relatively simple scheduling algorithm must be employed in that the ATM technique basically processes high-speed cells.
Conventional cell scheduling methods may roughly be classified into a WRR (Weighted Round Robin) cell scheduling method and a DRR (Deficit Round Robin) cell scheduling method.
With reference to FIGS. 2a and 2b, there is shown in block form the construction of a conventional DRR cell scheduling apparatus for implementation of the DRR cell scheduling method. As shown in these drawings, the conventional DRR cell scheduling apparatus comprises a plurality of input buffers 10 connected respectively to a plurality of connections i, a plurality of deficit counter (DC) storage tables 20 connected respectively to the input buffers 10, a queuing module 30, a multiplexer (Mux) 40, and an output buffer 50.
First, assume that a specific one of the input buffers 10, corresponding to a connection i as shown in FIG. 2a, is weighted “4”, and has a deficit counter (DC) value initialized to “0” and only two cells currently stored therein.
As a result, the queuing module 30 services the two cells currently stored in the specific input buffer 10, subtracts the number of the serviced cells from the weight of the buffer and then stores the resulting value in a specific one of the DC storage tables 20, corresponding to the specific input buffer 10.
Then, the Mux 40 receives two output cells from the specific input buffer 10 and in turn transfers them to the output buffer 50.
On the other hand, if the specific input buffer 10 has five cells stored therein, which are greater in number than the set weight, and a DC value of “1”, as shown in FIG. 2b, the queuing module 30 adds the DC value to the weight, services the five cells with the resulting value and then stores the remainder in the specific DC storage table 20. In FIG. 2b, the DC value “1” is again stored in the specific DC storage table 20.
However, the above-mentioned DRR cell scheduling method does not consider either a connection delay or cell loss. In this connection, the application of the DRR cell scheduling method to the VTOA of the IMT-2000 system disadvantageously necessitates the introduction of an algorithm considering data delays occurring during cell transfer, such as a packet fill delay (PFD), transfer delay and queuing delay, and an algorithm for discarding cells violating delay requirements.
Meanwhile, the conventional WRR cell scheduling method serves to schedule cells in each link on the basis of a weight predefined upon call establishment. Here, each weight is defined on the basis of an average data generation rate of an associated link, which can be obtained through a peak cell generation rate, average cell generation rate or etc.
However, the ATM cell scheduling in the above manner is desirable to guarantee the quality of service with respect to traffic with a constant cell generation rate, such as constant bit rate (CBR) traffic, but has difficulties in guaranteeing the quality of service and efficiently using a network bandwidth, with respect to traffic with an inconstant, or variable cell generation rate, such as variable bit rate (VBR) traffic.
Further in the above-mentioned WRR cell scheduling method, when a connection continuously transfers cells at a higher rate than an average transfer rate, it has an effect on the next connection, resulting in the lack of independence of each connection.
In brief, many studies have been made of the conventional WRR cell scheduling method and DRR cell scheduling method as mentioned above, in terms of fairness, or fair bandwidth allocation, but most of them have left the delay problem unnoticed and have been unable to readily implement the methods, leading to many difficulties in applying those methods to ATM services requiring real-time properties, such as the VTOA.
The conventional WRR cell scheduling method and DRR cell scheduling method have a further disadvantage in that they do not introduce a discard algorithm considering a delay parameter such as a cell transfer delay (CTD), so they cannot support the real-time VTOA service in an overload state of an output link when being applied to the ATM cell scheduling.